import java.util.HashMap;
import java.util.Map;

public class leetcode567_字符串的排列 {
    public static void main(String[] args) {
        Solution9 solution9 = new Solution9();
        System.out.println(solution9.checkInclusion("adc", "dcda"));

    }
}

// 滑动固定窗口解法，只有固定窗口内的字符串个数和s1相等   s1 的排列之一是 s2 的 子串才会成立
class Solution9 {
    public boolean checkInclusion(String s1, String s2) {
        // s1长度大于s2长度，必定不成立
        if (s1.length() > s2.length()) {
            return false;
        }
        int start = 0, end = s1.length();

        // 用于存放s1字符的map
        Map<Character, Integer> s1Map = new HashMap<>();
        // 用于存放s2字符的map
        Map<Character, Integer> windowMap = new HashMap<>();

        for (int i = 0; i < s1.length(); i++) {
            s1Map.put(s1.charAt(i), s1Map.getOrDefault(s1.charAt(i), 0) + 1);
        }

        // 计算第一个窗口的字符统计
        String s_start = s2.substring(start, end);
        for (int i = 0; i < s_start.length(); i++) {
            windowMap.put(s_start.charAt(i), windowMap.getOrDefault(s_start.charAt(i), 0) + 1);
        }

        while (end <= s2.length()) {
            if (windowMap.equals(s1Map)) {
                return true;
            }
            // 由于循环条件end <= s2.length()，=是为了取到s2末尾字符，当end=s2.length()时，s2.charAt(end)会发生越界，此处防止越界异常
            if (end >= s2.length()) break;

            // 滑动窗口右移动1个单位，当s2.charAt(end)存在时windowMap中时，让器计数值+1
            // 当s2.charAt(start)存在时windowMap中时，因为窗口右移动，让其计数值-1，当计数值为0时，删除
            windowMap.put(s2.charAt(end), windowMap.getOrDefault(s2.charAt(end), 0) + 1);
            windowMap.put(s2.charAt(start), windowMap.getOrDefault(s2.charAt(start), 0) - 1);
            if (windowMap.get(s2.charAt(start)) == 0) {
                windowMap.remove(s2.charAt(start));
            }
            end++;
            start++;
        }
        return false;
    }
}